|
In dieser Arbeit wird ein Zwei-Phasenmodell zur effizienten
Entfernungsberechnung in gewichteten Graphen untersucht. Bekannte
Anwendungsgebiete sind Verkehrsinformationssyteme, VLSI Design,
Verteiltes Rechnen und geometrische und parallele Algorithmen. In
einer Preprocessing-Phase wird zu einem Graphen ein Hierarchischer
Graph (HG) konstruiert, der in der Online-Phase zur
Entfernungsberechnung eingesetzt wird. Es werden die Laufzeit (T)
der Preprocessing-Phase, die Groesse (S) des HG'en und die
Laufzeit (Q) der Online-Phase untersucht. Zwei kontraere
Modellierungsansaetze werden vorgestellt: Geeignete Knoten und ein
rekursives Separationskonzept. Das Konzept mit Geeigneten Knoten
wird auf Levelgraphen verallgemeinert und es wird gezeigt, dass die
Berechnung einer minimalen Geeigneten Knotenmenge NP-vollstaendig
ist. Die Approximation bzgl. der Groesse der Geeigneten Knotenmenge
kann bis auf einen logarithmischen Faktor und bezueglich des
Umgebungsabstands bis auf einen konstanten Faktor in polynomieller
Laufzeit durchgefuehrt werden. Im Falle von planaren Graphen wird
mittels eines erweiterten Separationskonzepts (Ideen von Lingas 1990
und von Didjev 1996 werden kombiniert) gezeigt, dass HG'en von
fast linearer Groesse genuegen, um Q in O(n^{0.5} log^3 n) zu
gewaehrleisten. Dieses Resultat ist modulo logarithmischer Faktoren
optimal.
Ausserdem wird ein neuer Parameter 'Separatorweite' fuer
Graphen eingefuehrt und es wird konstruktiv gezeigt, dass die
Separatorweite unabhaengig von der Baumweite ist, aber hoechstens um
einen logarithmischen Faktor von der Baumweite abweicht. Am Beispiel
wird gezeigt, dass eine logarithmische Abweichung auftreten kann.
English:
In this work a two-phasemodel for efficient shortest-path-queries in
weighted graphs is examined. Applications are
traffic-information-systems, VLSI-design, distributed computing and
geometric and parallel algorithms. In a preprocessing-phase a
hierarchical graph (HG) is determined, which can be used efficiently
for answering shortest-path-queries in an online-phase. I examine
especially the running time of the preprocessing-phase (T) and of
the online-phase (Q) and the size of the HG (S). I present two
different approaches: appropriate vertices and a recursive
separation method. I generalize appropriate vertices to levelgraphs
and show the NP-completeness of the determination of a minimal
appropriate vertex set. For a minimal appropriate vertex set a
log-approximation and for the minimal surrounding distance a
2-approximation can be done in polynomial time. I give the
algorithms.
In the case of planar graphs I extend the separation method to
construct HG's of nearly linear size and show Q in O(n^{1.5}
log^3 n). This result is optimal modulo logarithmic factors.
Furthermore I introduce a new parameter for graphs called the
separatorwidth and show its independence of treewidth. Both
parameters differ at most up to a logarithmic factor. By giving an
example, I show that this can happen.
|